Codeforces Round 865 (Div. 2) ABCD

#Codeforces Round 865 (Div. 2) ABCD| 来源: 网络整理| 查看: 265

A. Ian Visits Mary——思维

思路

令直线为：l: y = kx，那么如果 l 只经过原点和终点 (a, b)，那么可以知道 k 必定为一个分数，那么可以知道 a、b 必定最大公约数为 1，即 a、b 互质。

因此如果 a、b 互质就可以一步到位。否则我们需要找一个点 (x_1, y_1)，使得 gcd(x1, y1) = 1、gcd(a - x_1, b - y1) = 1。不难发现，(1, b - 1)、(a, b) 即为两个符合要求的点。

代码

#include #define endl "\n" using namespace std; int n, a, b; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void solve() { cin >> a >> b; if(gcd(a, b) == 1) { cout

【本文地址】

公司简介

联系我们